package com.demoworld;

/**
 * Created by francis on 2017/7/6.
 * 单向链表
 */
public class JSingleLinkedList {
    public JSingleLinkedList() {
        this.length = 0;
        head = null;
        tail = null;
    }

    public JLinkedListStackNode head;
    public JLinkedListStackNode tail;
    public int length;

    public void add(int n) {
        JLinkedListStackNode tmpNode = new JLinkedListStackNode();
        tmpNode.value = n;
        tmpNode.next = null;

        if (this.length == 0 || head == null) {//添加第一个元素
            head = tmpNode;
            tail = head;
            this.length++;
            return;
        }
        if (head.next == null) {//添加第二个元素
            head.next = tmpNode;
            tail = head.next;
            this.length++;
            return;
        }
        tail.next = tmpNode;//添加第三个以及之后的元素， 添加完成后，记得重置尾巴指针
        tail = tail.next;
        this.length++;
    }

    public boolean remove(int n) {
        if (this.isEmpty()) {
            return true;
        }
        if (head.value == n) {
            head = head.next;
            return true;
        }
        return remove(n, head, head.next) != null;
    }

    private JLinkedListStackNode remove(int n, JLinkedListStackNode pre, JLinkedListStackNode current) {
        if (current == null) {
            return null;
        }
        if (current.value == n) {
            pre.next = current.next;
            return current;
        }
        return remove(n, current, current.next);
    }

    public boolean exist(int n) {
        if (isEmpty()) {//添加第一个元素
            return false;
        }
        JLinkedListStackNode node = _getByValue(n, this.head);
        return node != null;
    }

//每次修改新链表的头指针就好了， 这样就可以翻转
public JLinkedListStackNode reverseAndReturnHead() {
    JLinkedListStackNode tmpNewHead = null;

    JLinkedListStackNode tempOld = head;
    JLinkedListStackNode tempNew = null;

    tmpNewHead = new JLinkedListStackNode(null, tempOld.value);//新的链表
    while (tempOld.next != null) {
        tempNew = tmpNewHead;
        tmpNewHead = new JLinkedListStackNode();
        tmpNewHead.value = tempOld.next.value;
        tmpNewHead.next = tempNew;

        tempOld = tempOld.next;
    }
    return tmpNewHead;
}

    private JLinkedListStackNode _getByValue(int n, JLinkedListStackNode node) {
        if (node == null) {
            return null;
        }
        if (node.value == n) {
            return node;
        }
        return _getByValue(n, node.next);
    }

    public boolean isEmpty() {
        return this.length == 0;
    }
}
